#include <stdio.h>
#include <stdlib.h>

typedef struct Link_Queue Link_Queue_t ;
typedef struct Link_Queue* pLink_Queue_t;

typedef struct Queue_Node Queue_Node_t;
typedef struct Queue_Node* pQueue_Node_t;

//队列节点
struct Queue_Node
{
    int data;
    struct Queue_Node *next;
};

//队列
struct Link_Queue
{
    int size;
    //队头  始终指向首节点
    struct Queue_Node *front;
    //对尾  始终指向尾节点
    struct Queue_Node *rear;
};


//初始化队列
pLink_Queue_t Init_Link_Queue( void )
{
   pLink_Queue_t plink_queue = ( pLink_Queue_t )malloc( sizeof( Link_Queue_t ) );
   //初始化失败
   if( plink_queue == NULL )
   {
    perror( "malloc queue fail" );
    return NULL;
   }
   //初始化成功
   plink_queue->size = 0;
   plink_queue->front = NULL;
   plink_queue->rear = NULL;
   return plink_queue;
}

//普通情况的时候就和链表尾插法一样
void Push_Queue( pLink_Queue_t plink_queue,int data )
{
    pQueue_Node_t pnew = ( pQueue_Node_t )malloc( sizeof( pQueue_Node_t ) );
    if( pnew == NULL)
    {
        perror( "malloc a queue node fail\n" );
        return ;
    }
    //队列里无节点时
    //队列判断有无节点可以通过size 或者front和rear
    if( plink_queue->size == 0 )
    {
        //先自己
        pnew->data = data;
        pnew->next = NULL;
        //后别人
        plink_queue->front = pnew;
        plink_queue->rear = pnew;
        plink_queue->size++;
        return ;
    }
    //一般情况，队头指针不需要动，队尾指针需要动
    //先自己
    pnew->data = data;
    pnew->next = NULL;
   
    //后别人
    plink_queue->rear->next = pnew;
    plink_queue->rear = pnew;
    plink_queue->size++;
    
    return ;
}

//出列
void Pop_Link_Queue(pLink_Queue_t plink_queue)
{
    if( plink_queue->size == 0 )
    {
        printf( "队列无节点\n" );
        return ;
    }

    pQueue_Node_t pqueue_node = plink_queue->front;

    //队列只有一个节点的时候
    if( plink_queue->size == 1 )
    {
        free( pqueue_node );
        plink_queue->front = NULL;
        plink_queue->rear = NULL;
        plink_queue->size--;
        return ;
    }
    //出列操作
    plink_queue->front = pqueue_node->next;
    plink_queue->size--;
    free( pqueue_node );

    return ;
}

int Pop_and_get_Link_Queue(pLink_Queue_t plink_queue)
{
    if( plink_queue->size == 0 )
    {
        printf( "队列无节点\n" );
        return -1;
    }

    pQueue_Node_t pqueue_node = plink_queue->front;
    //获取出列节点的数据
    int data = pqueue_node->data;
    //队列只有一个节点的时候
    if( plink_queue->size == 1 )
    {
        free( pqueue_node );
        plink_queue->front = NULL;
        plink_queue->rear = NULL;
        plink_queue->size--;
        return data;
    }
    

    //出列操作
    plink_queue->front = pqueue_node->next;
    plink_queue->size--;
    free( pqueue_node );

    return data;
}


//打印队列
void Print_Link_Queue( pLink_Queue_t plink_queue )
{
    if( plink_queue->size == 0 )
    {
        printf( "None node in link queue\n" );
        return ;
    }
    pQueue_Node_t pqueue_node = plink_queue->front;

    printf("队头-> ");
    while( pqueue_node != NULL )
    {
        printf( "%d ",pqueue_node->data );
        pqueue_node = pqueue_node->next;
    }
    printf(" <-队尾\n");
    return ;
}


//摧毁队列
void Destory_Link_Queue(pLink_Queue_t plink_queue)
{
    //普通情况
   if( plink_queue->size == 0 )
   {
    free( plink_queue );
    printf( "plink_queue is NULL" );
    return ;
   }
   //释放队列节点
   pQueue_Node_t pqueue_node = plink_queue->front;
   pQueue_Node_t ptmp = NULL;
   while( pqueue_node != NULL )
   {
    ptmp = pqueue_node->next;
    free( pqueue_node );
    pqueue_node = ptmp;
   }
   //释放队列
   free( plink_queue );
   printf("成功释放队列\n");
   return ;
}


int main(){
    pLink_Queue_t plink_queue = Init_Link_Queue();
    if( plink_queue == NULL )
    {
        perror( "init queue fail" );
        return -1;
    }

    #if 1
    Push_Queue( plink_queue,1 );
    Push_Queue( plink_queue,2 );
    Push_Queue( plink_queue,3 );
    Push_Queue( plink_queue,4 );
    Push_Queue( plink_queue,5 );
    #endif 

    #if 0
    Pop_Link_Queue( plink_queue );
    Pop_Link_Queue( plink_queue );
    Pop_Link_Queue( plink_queue );
    Pop_Link_Queue( plink_queue );
    Print_Link_Queue( plink_queue );
    Pop_Link_Queue( plink_queue );
    #endif 

    //获取出队列的数据
    #if 1
    while( plink_queue->size != 0 )
    {
        int data = Pop_and_get_Link_Queue( plink_queue );
        printf( "出列节点数据为：%d\n",data );
    }
    #endif
    
    //打印队列数据
    #if 0
    Print_Link_Queue( plink_queue );
    #endif

    Destory_Link_Queue(plink_queue);
    plink_queue = NULL;


    return 0;
}